/*
 * nwpu/2005/2005_2.c
 *
 * Harry Wei <harryxiyou@gmail.com> (C) 2013
 */
#include <stdio.h>
#include <stdlib.h>

struct node {
	int val;
	struct node *order;
	struct node *sort;
};

int main(int argc, char *argv[]) {
	int d = 0;
	struct node *h = NULL;
	struct node *u = NULL;
	struct node *v = NULL;
	struct node *p = NULL;
	struct node *tail = NULL;

	h = (struct node *) malloc(sizeof(struct node));
	if (NULL == h) {
		fprintf(stderr, "%s\n", "Allocate error!");
		return -1;
	}
	tail = h;
	tail->sort = NULL;
	fprintf(stdout, "%s", "Please input data:");
	do {
		scanf("%d", &d);
		if (0 < d) {
			p = (struct node *)malloc(sizeof(struct node));
			if (NULL == p) {
				fprintf(stderr, "%s\n", "Allocate error!");
				return -1;
			}
			p->val = d;
			tail->order = p; /*first answer*/
			tail = p;
			/*second answer*/
			for (u = h, v = u->sort; v && v->val < d; v = v->sort, u = u->sort);
			p->sort = v;
			u->sort = p; /*third answer*/
		}
	} while (d > 0);
	tail->order = NULL; /*forth answer*/
	p = h->sort;
	while (p) {
		printf("%d, ", p->val);
		p = p->sort;
	}
	printf("\n\n");
	for (p = h->order; p; p = p->order) {
		printf("%d, ", p->val);
	}
	/*TODO: free jobs, now, os do those*/
	printf("\n\n");
	return 0;
}
